﻿#pragma once

#include <iostream>
#include <vector>
#include <time.h>
#include <thread>
#include <algorithm>
#include <assert.h>
#include <mutex>
#include <unordered_map>
//之前这里现有一个ObjectPool的头文件，那在这里先展开了  导致编译器编译从上往下找的时候没有找到

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;	// 哈希桶的数量
static const size_t NPAGES = 129; 		// 最大挂128页的span，为了让桶号与页号对应起来，我们可以将第0号桶空出来，因此我们需要将哈希桶的个数设置成129。	
static const size_t PAGE_SHIFT = 13;	// 2^13 = 8192 8KB


// 为什么 _WIN32 放在前面会出错？
// 因为在 64 位 Windows 环境下，先检查 _WIN32，由于 _WIN32 总是被定义，条件 #ifdef _WIN32 会直接成立
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	// ...
#endif



#ifdef _WIN32
	#include<windows.h>
#else
	// ...
#endif


// 直接在堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
	#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
	#else
		// linux下brk mmap等
	#endif

	if (ptr == nullptr)
			throw std::bad_alloc();

	return ptr;
}


// 在堆上释放空间
inline static void SystemFree(void* ptr)
{
	#ifdef _WIN32
		VirtualFree(ptr, 0, MEM_RELEASE);
	#else
		// linux下brk mmap等
	#endif
}



static void*& NextObj(void* obj) {
	// 转换为 void** 类型，再解引用，得到下一个对象的内存地址
	// obj是一个指针，指向一个对象的内存地址
		//  对象内存地址
		// [ next_ptr (8字节) ][ 对象数据 (sizeof(T)字节) ]
			// obj 是对象的起始地址
			// void** pp = (void**)&obj; // pp 指向 obj 的地址（即对象内存的起始位置）
			// return *(void**)obj; // 取出下一个对象的内存地址	
	return *(void**)obj;
}


// 管理切分好的小对象的自由链表
class FreeList {
	public:
		void Push(void* obj) {
			assert(obj);
			// 头插
			NextObj(obj) = _freeList;
			_freeList = obj;

			++_size;
		}

		// 将新分配的内存块放入链表中
		void PushRange(void* start, void* end, size_t n) {
			NextObj(end) = _freeList;
			_freeList = start;


			// 检查是否有n个对象
			int i = 0;
			void* cur = start;
			while (cur) {
				cur = NextObj(cur);
				++i;
			}
			if (i != n) {
				// 条件断点
				int x = 0;
			}

			_size += n;
		}

		void PopRange(void*& start, void*& end, size_t n) {
			assert(n <= _size);
			start = _freeList;
			end = start;

			for (size_t i = 0; i < n - 1; ++i) {
				end = NextObj(end);
			}

			_freeList = NextObj(end);
			NextObj(end) = nullptr;
			_size -= n;
		}

		void* Pop() {
			assert(_freeList);

			// 头删
			void* obj = _freeList;
			_freeList = NextObj(obj);
			--_size;
			
			return obj;
		}

		bool Empty() {
			return (_freeList == nullptr);
		}

		size_t& MaxSize() {
			return _maxSize;
		}

		size_t& Size() {
			return _size;
		}

	private:
		void* _freeList = nullptr;
		size_t _maxSize = 1;

		size_t _size = 0;
};




// 计算对象大小的对齐映射规则
class SizeClass {
	public:
		// ​小对象​（1~128字节）：对齐到 8 字节，分配到自由列表的前 16 个槽位（索引 0~15）。
		//​ 中等对象​（129~1024字节）：对齐到 16 字节，分配到索引 16~71。
		// 大对象​（1025~81024字节）：对齐到 128 字节，分配到索引 72~127。
		// 超大对象：对齐到更高粒度（如 1024、8192 字节），避免大对象占用过多小内存块。
		
		// 整体控制在最多10%左右的内碎?浪费
			// [1,128]					8byte对?			freelist[0,16)
			// [128+1,1024]			16byte对?		freelist[16,72)
			// [1024+1,81024]			128byte对?		freelist[72,128)
			// [8*1024+1,641024]		1024byte对?		freelist[128,184)
			// [64*1024+1,256*1024]	8*1024byte对?	freelist[184,208)
		
		// version - 1 普通人版
		// 将请求的内存大小调整为对齐后的整数倍。
			// size 当前请求的内存大小
			// alignNum 对齐数
			// alignSize 对齐后的内存大小
		//size_t _RoundUp(size_t size, size_t alignNum) {
		//	size_t alignSize ;
		//	if (size % alignNum != 0) {
		//		alignSize = (size / alignNum + 1) * alignNum;
		//	}
		//	else {
		//		alignSize = size;
		//	}
		//	return alignSize;
		//}

		// version - 2 进阶版
		// 通过位运算来实现对齐计算，避免了除法和乘法的开销。
			// size 当前请求的内存大小
			// alignNum 对齐数
			// alignSize 对齐后的内存大小
		static inline size_t _RoundUp(size_t size, size_t alignNum) {
			return ((size + alignNum - 1) & ~(alignNum - 1));
		}

		// 计算对齐后的内存大小
		static inline size_t RoundUp(size_t size) {
			if (size <= 128) {
				return _RoundUp(size, 8); // 对齐到 8 字节
			}
			else if (size <= 1024) {
				return _RoundUp(size, 16); // 对齐到 16 字节
			}
			else if (size <= 8 * 1024) {
				return _RoundUp(size, 128); // 对齐到 128 字节
			}
			else if (size <= 64 * 1024) {
				return _RoundUp(size, 1024);
			}
			else if (size <= 256 * 1024) {
				return _RoundUp(size, 8 * 1024);
			}
			else {
				return _RoundUp(size, 1 << PAGE_SHIFT);
			}
		}


		static inline size_t _Index(size_t bytes, size_t align_shift)
		{
			return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		}

		// 计算映射的哪一个自由链表桶
		static inline size_t Index(size_t bytes)
		{
			assert(bytes <= MAX_BYTES);

			// 每个区间有多少个链
			static int group_array[4] = { 16, 56, 56, 56 };
			if (bytes <= 128) {
				return _Index(bytes, 3);
			}
			else if (bytes <= 1024) {
				return _Index(bytes - 128, 4) + group_array[0];
			}
			else if (bytes <= 8 * 1024) {
				return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
			}
			else if (bytes <= 64 * 1024) {
				return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
			}
			else if (bytes <= 256 * 1024) {
				return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
			}
			else {
				assert(false);
			}

			return -1;
		}
		

		// 一次 thread cache 从中心缓存中获取多少个
		static size_t NumMoveSize(size_t size) {
			assert(size > 0);

			// [2, 512], 一次批量多少个对象的上下限值
			int num = MAX_BYTES / size;

			// 确保至少获取两个对象，避免极端情况下多次请求（如 size=256KB 时 MAX_BYTES/size=1），减少与 CentralCache 的交互频率。
			if(num < 2) num = 2;

			// 若单次申请过多对象（如 MAX_BYTES/size = 32768），ThreadCache 可能缓存大量未使用的内存块，导致 ​内存浪费。
			if(num > 512) num = 512;

			return num;
		}

		static size_t NumMovePage(size_t size) {
			// 计算出thread cache一次向central cache申请对象的个数上限
			size_t num = NumMoveSize(size);
			// num 个size 大小的对象所需的字节数
			size_t npage = num * size;

			npage >>= PAGE_SHIFT;
			if(npage == 0)
				npage = 1;
			
			return npage;
		}
		
};



// 管理多个连续页大块内存跨度结构
struct Span {
	PAGE_ID _PAGEID = 0;	// 大块内存起始页的页号
	size_t _n = 0;			// 页的数量

	Span* _next = nullptr;	// 双向链表的结构
	Span* _prev = nullptr; 

	size_t _objectSize = 0; // 切好的小对象的大小
	size_t _userCount = 0;	// 已分配给 Thread Cache 的小块内存数量
	void* _freeList = nullptr; // 自由链表头指针（指向未分配的小块内存）

	bool _isused = false;	// 是否在被使用
};


class SpanList {
	public:
		SpanList() {
			_head = new Span;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 获取开头节点
		Span* Begin(){
			return _head->_next;
		}

		// 获取哨兵位
		Span* End(){
			return _head;
		}

		// 判空
		bool Empty() {
			return _head->_next == _head;
		}

		// 头插
		void PushFront(Span* span) {
			Insert(Begin(), span);
		}

		// 返回头结点
		Span* PopFront() {
			Span* front = _head->_next;
			assert(front != _head);
			Erase(front);
			return front;
		}

		// 插入
		void Insert(Span* pos, Span* newSpan) {
			assert(pos);
			assert(newSpan);

			Span* prev = pos->_prev;
			prev->_next = newSpan;
			newSpan->_prev = prev;
			newSpan->_next = pos;
			pos->_prev = newSpan;
		}

		// 删除
		// 注意：从双链表删除的span会还给下一层的page cache，相当于只是把这个span从双链表中移除，因此不需要对删除的span进行delete操作。
		void Erase(Span* pos) {
			assert(pos);
			// 不能删除哨兵位
			// 条件断点
			//assert(pos != _head);
			if (pos == _head) {
				// 写一句不干扰外面代码的语句
				int x = 0;
			}
			
			// 删除 pos 结点
			Span* prev = pos->_prev;
			Span* next = pos->_next;
			prev->_next = next;
			next->_prev = prev;
		}

	private:
		Span* _head;
	public:
		std::mutex _mtx; // 桶锁
};


